package strategy;

import java.util.Scanner;

public  class Square implements Graph{

	@Override
	public void draw() {
		System.out.println("");
	}
	
	public static void main(String[] args){
		//int [] pre = {1,2,4,7,3,5,6,8};
		int [] in = {4,7,2,1,5,3,8,6};
		heapSort(in);
		for(int t: in){
		    System.out.print(t);
		}
	}
	
	public static void heapSort(int[] arr){
		for(int i = (arr.length - 1)/2; i >= 0; i--){
			adjustHeap(arr,i,arr.length);
		}
		for(int i = arr.length - 1; i > 0; i--){
			swap(arr,0,i);
			adjustHeap(arr,0,i);
		}
	}
	
	public static void adjustHeap(int[] arr,int i,int length){
		for(int y = 2*i+1;y<length; y = 2*y+1){
			if(y + 1 < length && arr[y+1] > arr[y]){
				y++;
			}
			if(arr[i] < arr[y]){
				int temp = arr[y];
				arr[y] = arr[i];
				arr[i] = temp;
				i = y;
			}
		}
	}
	
	public static void swap(int[] arr,int a,int b){
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	
	public static void quickSort(int[] arr){
		quick(arr,0,arr.length-1);
	}
	
	public static void quick(int[] arr,int begin,int end){
		int x = begin,y = end;
		if(x >= y){
			return ;
		}
		int part = 0;
		while(x < y){
			if(part == 1){
				if(arr[x] <= arr[begin])
				   x++;
				else{
					int temp = arr[y];
					arr[y] = arr[x];
					arr[x] = temp;
					part = 0;
				}
			}
			else if(part == 0 ){
				if(arr[y] >= arr[begin])
				    y--;
				else
				   part = 1;
			}
			
		}
		if(x == y){
			int temp = arr[begin];
			arr[begin] = arr[x];
			arr[x] = temp;
		}
		quick(arr,begin,x-1);
		quick(arr,x+1,end);
	}
	
	public static void insertSort(int[] arr){
		int length = arr.length;
		for(int i = 1; i < length - 1; i++){
			for(int j = 0; j <= i; j++){
				if(arr[i+1] < arr[j]){
					int temp = arr[i+1];
					for(int x = i; x >= j; x--){
						arr[x + 1] = arr[x];
					}
					arr[j] = temp;
				}
			}
		}
	}
	
	public static void selectionSort(int[] arr){
		int length = arr.length;
		for(int i = 0; i < length - 1; i++){
			int min = Integer.MAX_VALUE;
			int min_lo = 0;
			for(int j = i + 1; j < length; j++){
				if(arr[j] < min){
					min = arr[j];
					min_lo = j;
				}
			}
			if(min < arr[i]){
				arr[min_lo] = arr[i];
				arr[i] = min;
			}
		}
	}
	
    
     public static void mergeSort(int[] arr){
    	 int length = arr.length;
    	 int[] temp = new int[length];
    	 mergeSort(arr,0,length - 1,temp);
     }
     
     public static void mergeSort(int[] arr,int begin,int end,int[] temp){
    	 if(begin < end){
    		 int mid = (end+begin)/2;
    		 mergeSort(arr,begin,mid,temp);
        	 mergeSort(arr,mid + 1,end,temp);
        	 merge(arr,begin,end,temp);
    	 }
    	 
     }
     
     public static void merge(int[] arr,int begin,int end,int[] temp){
    	 int mid = (end+begin)/2 + 1;
    	 int i = begin;
    	 int j = mid;
    	 int t = 0;
    	 while(i < mid && j <= end){
    		 if(arr[i] < arr[j]){
    			 temp[t++] = arr[i++];
    		 }
    		 else{
    			 temp[t++] = arr[j++];
    		 }
    	 }
    	 while(i < mid){
    		 temp[t++] = arr[i++];
    	 }
    	 while(j <= end){
    		 temp[t++] = arr[j++];
    	 }
    	 int x = begin;
    	 while(x <= end){
    		 arr[x] = temp[x - begin];
    		 x++;
    	 }
     }

	
     
}

 